1. Field of Invention
The field of this invention is cryptography. This invention relates to cryptosystems, and in particular to the escrowing and recovering of cryptographic keys and data encrypted under cryptographic keys. The escrow and recovery process assures that authorized entities like law-enforcement bodies, government bodies, users, and organizations, can when allowed or required, read encrypted data. The invention relates to cryptosystems implemented in software or in hardware. In particular, the invention relates to the generation of user public keys based on general exponentiation such as: the discrete logarithm problem, the problem of modular root extraction, and the problem of factoring. The mechanisms are secure and do not reduce the security of the underlying exponentiation cipher.
2. Description of Prior Art
Public Key Cryptosystems (PKC's) allow secure communications between two parties who have never met before. The notion of a PKC was put forth in (W. Diffie, M. Hellman, "New directions in cryptography", IEEE Transactions on Information Theory, 22, pages 644-654, 1976). This communication can take place over an insecure channel. In a PKC, each user possesses a public key E and a private key D. E is made publicly available by a key distribution center, also called certification authority (CA), after the registration authority verifies the authenticity of the user (its identification, etc.). The registration authority is part of the certification authority. D is kept private by the user. E is used to encrypt messages, and only D can be used to decrypt messages. It is computationally impossible to derive D from E. To use a PKC, party A obtains party B's public key E from the key distribution center. Party A encrypts a message with E and sends the result to party B. B recovers the message by decrypting with D. The key distribution center is trusted by both parties to give correct public keys upon request. A PKC based on the difficulty of computing discrete logarithms was published in (T. ElGamal, "A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms", CRYPTO '84, pages 10-18, Springer-Verlag, 1985).
The current invention relates to key escrow systems. Prior methods for conducting key escrow are U.S. Pat. Nos. 5,276,737, and 5,315,658 to Micali (1994). In these patents Micali discloses a Fair Public Key Cryptosystem (FPKC) which is based on the work of P. Feldman (28th annual FOCS). The FPKC solution is not as efficient in terms of use as Auto-Recoverable and Auto-Certifiable Cryptosystems as users in a public key infrastructure need to communicate with escrow authorities. Furthermore, It has been shown that the Fair RSA PKC does not meet certain needs of law enforcement (J. Kilian, F. Leighton, "Fair Cryptosystems Revisited", CRYPTO '95, pages 208-221, Springer-Verlag, 1995), since a shadow public key cryptosystem can be embedded within it. A shadow public key system is a system that can be embedded in a key escrow system that permits conspiring users to conduct untappable communications. Kilian and Leighton disclose a Fail-safe Key Escrow system. This system has the drawback that it requires users to engage in a costly multi-round protocol in order to generate public/private key pairs. Other key escrow systems with similar inefficiencies are by De Santis et al., Walker and Winston (TIS), and the IBM SecureWay document. These solutions propose session-level escrow which requires changes in communication protocols so that the session headers in the communication protocol carry encrypted key-related information. A "Fraud-Detectable Alternative to Key-Escrow Proposals" based on ElGamal has been described in (E. Verheul, H. van Tilborg, "Binding ElGamal: A Fraud-Detectable Alternative to Key-Escrow Proposals", Eurocrypt '97, pages 119-133, Springer-Verlag, 1997). This system, called Binding ElGamal, provides for session level key recoverability, and makes no provision for preventing users from encrypting messages using the provided unescrowed public key infrastructure prior to using the Binding ElGamal system. Hence, it permits conspiring criminals to conduct untappable communications. Binding ElGamal also imposes a large amount of communication overhead per communications session and changes in communication protocol headers. An overview of key escrow schemes appears in (D. Denning, D. Branstad, "A Taxonomy for Key Escrow Encryption Systems," Communications of the ACM, v. 39, n. 3, 1996). In (N. Jefferies, C. Mitchell, M. Walker, "A Proposed Architecture for Trusted Third Party Services", Cryptography: Policy and Algorithms, LNCS 1029, Springer, 1996) and (R. Anderson, "The GCHQ Protocol and Its Problems" , Eurocrypt '97, pages 134-148, Springer-Verlag, 1997) a trusted third party approach to escrow is described where the trusted third parties of the participating users are involved in every session key establishment stage, and hence provides for another cumbersome solution as well.
In the pending U.S. patent Ser. Nos. 08/864,839, 08/878,189, 08/920,504, and 08/932,639, Auto-Recoverable and Auto-Certifiable public key cryptosystems were disclosed that have the following properties. Users of the system can generate a public/private key pair and a certificate of recoverability. This certificate of recoverability can be used to both recover the private key by the escrow authorities, and verify that the private key is recoverable. No changes in communication protocols are required. Also, no communication between users and the escrow authorities are required. The main restriction of the prior Auto-Recoverable and Auto-Certifiable cryptosystems that were proposed is that they each use specific mechanisms to hide the key information to the escrow authorities inside the certificate of recoverability. Each of the systems is limited to a specific cipher system. What is needed is a new auto-recoverable and auto-certifiable key escrow solution which uses a generic mechanism to hide key information inside the certificate of recoverability. This generic method should not reduce the security of the cipher system. A generic mechanism is a mechanism that does not limit the cipher system of the escrow authorities, and in a generic mechanism any public key encryption method can be employed. The goal of the present invention is to solve this problem. The present invention shows how to employ general public key ciphers for the escrow authorities and general exponentiation ciphers for the users in order to implement Auto-Recoverable and Auto-Certifiable key systems. The present invention discloses two solutions to the problem of key escrow using two instances of exponentiation ciphers. The first solution is based on the discrete log problem, and the second solution is based on the difficulty of factoring. Cryptosystems based on factoring, i.e., systems based on a multiplication of two large prime numbers, e.g., the RSA system by Rivest et. al. (Rivest 1983), are very popular. The present invention is applicable to all known exponentiation ciphers for the users. The invention discloses a method in which the certificate of recoverability does not reduce the security of the overall system. The present invention shows how to replace a public key infrastructure where users register their keys with a certification authority of an escrowed PKI using the same protocol messages. This is accomplished by changing the key generation mechanism and message content. This minimal change is due to the fact that the present invention is applicable to cipher systems in use in current PKI systems. We call this minimal changing mechanism "protocol embedding".
Auto-Recoverable and Auto-Certifiable Cryptosystems solutions employ the use of non-interactive proofs in computing the certificate of recoverability. More specifically, they employ a technique analagous to the Fiat Shamir non-interactive proof technique which is disclosed in (A. Fiat, A. Shamir, "How to Prove Yourself: Practical Solutions to Identification and Signature Problems", CRYPTO '86, pages 186-194, Springer-Verlag, 1987). It is known in the art how to replace such non-interactive proofs by interactive proofs. The new variant of proofs introduced by our mechanism is a proof that combines a zero-knowledge methodology with explicit encryptions of values to a third party.